0096. 不同的二叉搜索树【中等】
1. 📝 题目描述
给你一个整数 n,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:

txt
输入:n = 3
输出:51
2
2
示例 2:
txt
输入:n = 1
输出:11
2
2
提示:
1 <= n <= 19
2. 🎯 s.1 - 动态规划(卡特兰数)
c
int numTrees(int n) {
int dp[n + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
dp[i] += dp[j - 1] * dp[i - j]; // 左子树 * 右子树
return dp[n];
}1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
js
/**
* @param {number} n
* @return {number}
*/
var numTrees = function (n) {
const dp = new Array(n + 1).fill(0)
dp[0] = 1
dp[1] = 1
for (let i = 2; i <= n; i++)
for (let j = 1; j <= i; j++) dp[i] += dp[j - 1] * dp[i - j] // 左子树 * 右子树
return dp[n]
}1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
py
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j] # 左子树 * 右子树
return dp[n]1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
- 时间复杂度:
,双层循环填表 - 空间复杂度:
,dp数组的大小
算法思路:
dp[i]表示i个节点能组成的不同 BST 的数量,即卡特兰数- 枚举每个节点
j作为根,左子树有j-1个节点,右子树有i-j个节点 - 转移方程:
- 初始化:
,空树和单节点树各有 1 种